#include "avl_tree.h"

int GetNodeHeight(AVLNode* node){

    if(node == nullptr){
        return 0;
    }

    return node->height;
}

AVLNode* CreateNode(int value){

    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));

    node->value = value;

    node->left = node->right = nullptr;

    node->height = 1;

    return node;
}

int Max(int a,int b){
    return (a > b) ? a : b;
}

AVLNode* RightRotate(AVLNode* unbalance_node){

    //stores new root node and moving subtree
    AVLNode* new_root = unbalance_node->left;
    AVLNode* subtree = new_root->right;

    //right rotation opteration
    new_root->right = unbalance_node;
    unbalance_node->left = subtree;

    //update height of unbalance node and new root
    unbalance_node->height = Max(GetNodeHeight(unbalance_node->left),GetNodeHeight(unbalance_node->right)) + 1;
    new_root->height = Max(GetNodeHeight(new_root->left),GetNodeHeight(new_root->right)) + 1;

    return new_root;
}

AVLNode* LeftRotate(AVLNode* unbalance_node){

    //stores new root node and moving subtree
    AVLNode* new_root = unbalance_node->right;
    AVLNode* subtree = new_root->left;

    //right rotation opteration
    new_root->left = unbalance_node;
    unbalance_node->right = subtree;

    //update height of unbablance and new root
    unbalance_node->height = Max(GetNodeHeight(unbalance_node->left),GetNodeHeight(unbalance_node->right)) + 1;
    new_root->height = Max(GetNodeHeight(new_root->left),GetNodeHeight(new_root->right)) + 1;

    return new_root;
}

AVLNode* LeftRightRotate(AVLNode* unbalance_node){

    //rotate left tree first
    unbalance_node->left =  LeftRotate(unbalance_node->left);

    //rotate unbalance node then
    return RightRotate(unbalance_node);
}

AVLNode* RightLeftRotate(AVLNode* unbalance_node){

    //rotate right tree first
    unbalance_node->right =  RightRotate(unbalance_node->right);

    //rotate unbalance node then
    return LeftRotate(unbalance_node);
}

int GetBalanceFactor(AVLNode* node){
    if(node == nullptr) return 0;
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}

AVLNode* InsertNode(AVLNode* node,int value){

    if(node == nullptr) return CreateNode(value);

    if(value < node->value)
        node->left  = InsertNode(node->left,value);
    else if(value > node -> value)
        node->right = InsertNode(node->right,value);
    else
        return node;

    node->height = 1 + Max(GetNodeHeight(node->left),GetNodeHeight(node->right));

    int balancefactor = GetBalanceFactor(node);

    //LL
    if(balancefactor > 1 && value < node->left->value)
        return RightRotate(node);

    //RR
    if(balancefactor < -1 && value > node->right->value)
        return LeftRotate(node);

    //LR
    if(balancefactor > 1 && value > node->left->value)
        return LeftRightRotate(node);

    //RR
    if(balancefactor < -1 && value < node->right->value)
        return RightLeftRotate(node);

    return node;
}

AVLNode* FindMinValueNode(AVLNode* node){

    AVLNode* current = node;
    while(current->left != nullptr)
        current = current->left;
    return current;
}

AVLNode* FindMaxValueNode(AVLNode* node){

    AVLNode* current = node;
    while(current->right != nullptr)
        current = current->right;
    return current;
}

AVLNode* DeleteNode(AVLNode* root,int value){

    if(root == nullptr) return root;

    if(value < root->value)
        root -> left = DeleteNode(root->left,value);
    else if(value > root->value)
        root->right = DeleteNode(root->right,value);
    else{
        if((root->left == nullptr) || (root->right == nullptr)){
            AVLNode* tempnode = root->left?root->left:root->right;
            if(tempnode == nullptr){
                tempnode = root;
                root = nullptr;
            }else
                *root = *tempnode;
            free(tempnode);
        }else{
            AVLNode* tempnode = FindMinValueNode(root->right);
            root->value = tempnode->value;
            root->right = DeleteNode(root->right,tempnode->value);
        }
    }
    if(root == nullptr) return root;

    root->height = 1 + Max(GetNodeHeight(root->left),GetNodeHeight(root->right));

    int balancefactor = GetBalanceFactor(root);

    //LL
    if(balancefactor > 1 && value < root->left->value)
        return RightRotate(root);

    //RR
    if(balancefactor < -1 && value > root->right->value)
        return LeftRotate(root);

    //LR
    if(balancefactor > 1 && value > root->left->value)
        return LeftRightRotate(root);

    //RR
    if(balancefactor < -1 && value < root->right->value)
        return RightLeftRotate(root);

    return root;
}

AVLNode* SearchNode(AVLNode* root,int value){

    if(root == nullptr || root -> value == value)   return root;

    if(root->value < value) return SearchNode(root->right,value);

    return SearchNode(root->left,value);
}

void PreOrderTraverse(AVLNode* root){

    if(root != nullptr){

        printf("%d ",root->value);

        PreOrderTraverse(root->left);

        PreOrderTraverse(root->right);
    }
}

void MidOrderTraverse(AVLNode* root){

    if(root != nullptr){

        MidOrderTraverse(root->left);

        printf("%d ",root->value);

        MidOrderTraverse(root->right);
    }
}

void PostOrderTraverse(AVLNode* root){

    if(root != nullptr){

        PostOrderTraverse(root->left);

        PostOrderTraverse(root->right);

        printf("%d ",root->value);
    }
}

void DestroyTree(AVLNode* root){
    if(root != nullptr){
        DestroyTree(root->left);
        DestroyTree(root->right);
        free(root);
    }
}


